package sort;

/**
 * @author way
 * @create 2025-03-17 21:22
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = new int[]{5, 4, 3, 8, 2, 7, 9, 1};
        HeapSort heapSort = new HeapSort();
        heapSort.sort2(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public void sort2(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        int n = a.length;
        //先构造堆
        buildHeapBySwim(a);
        while (n > 0) {
            //交换根节点和最后一个元素的位置，即是删除堆顶元素
            swap(a, 0, --n);
            sink(a, 0, n);
        }
    }


    public void sort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        int n = a.length;
        //先构造堆 自下而上的下滤；自下而上的下滤类似于从最后一个非叶子节点开始往前删除，本质为删除。
        for (int k = n / 2 - 1; k >= 0; k--) {
            sink(a, k, n);
        }
        while (n > 0) {
            //交换根节点和最后一个元素的位置，即是删除堆顶元素
            swap(a, 0, --n);
            sink(a, 0, n);
        }
    }

    // 方式2：逐个插入建堆（自下而上，时间复杂度 O(n log n)）
    public void buildHeapBySwim(int[] a) {
        for (int k = 1; k < a.length; k++) {
            swim(a, k);
        }
    }

    /**
     * @param k 当子节点“变得”>父节点时，需要将子节点从下层到上层移动（上浮）
     */
    void swim(int[] a, int k) {
        while (k > 0 && a[k] > a[(k-1)/2]) {
            swap(a, k, (k-1)/2);
            k = (k-1)/2;
        }
    }

    /**
     * 下沉操作
     * 最后一个非叶子节点为k=(堆大小/2)-1
     *
     * @param a 数组
     * @param k 待下沉元素
     * @param N 数组中最后一个元素的索引
     */
    void sink(int[] a, int k, int N) {
        while (2 * k + 1 < N) { //非叶子节点
            int j = 2 * k + 1; // 左右节点较大的
            //左右子节点中取较大值
            if (j + 1 < N && a[j] < a[j + 1]) {
                j++;
            }
            //如果待下沉元素>左右子节点的最大值，则停止下沉
            if (a[k] >= a[j]) {
                break;
            }
            //左右子节点的大小关系不确定，所以这里只和较大子节点进行交换
            swap(a, j, k);
            k = j;
        }
    }

    public void swap(int[] a, int i, int j) {
        int temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
